Learning Deterministic Regular Expressions for the Inference of Schemas from XML Data

摘要

Inferring an appropriate DTD or XML Schema Definition (XSD) for a givencollection of XML documents essentially reduces to learning deterministicregular expressions from sets of positive example words. Unfortunately, thereis no algorithm capable of learning the complete class of deterministic regularexpressions from positive examples only, as we will show. The regularexpressions occurring in practical DTDs and XSDs, however, are such that everyalphabet symbol occurs only a small number of times. As such, in practice itsuffices to learn the subclass of deterministic regular expressions in whicheach alphabet symbol occurs at most k times, for some small k. We refer to suchexpressions as k-occurrence regular expressions (k-OREs for short). Motivatedby this observation, we provide a probabilistic algorithm that learns k-OREsfor increasing values of k, and selects the deterministic one that bestdescribes the sample based on a Minimum Description Length argument. Theeffectiveness of the method is empirically validated both on real world andsynthetic data. Furthermore, the method is shown to be conservative over thesimpler classes of expressions considered in previous work.